// 2025/8/20
// 最小的完全平方数

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> dp(n + 1, n);
    dp[0] = 0;
    for(int i = 1; i * i <= n; i++)
    {
        int cur = i * i;
        for(int j = 1; j <= n; j++)
        {
            if(cur <= j && dp[j - cur] != n)
                dp[j] = min(dp[j], dp[j - cur] + 1);
        }
    }
    cout << dp[n] << endl;
}
// 64 位输出请用 printf("%lld")